package priv.conceit.study.leetcode.simple.official;


import java.util.*;
import java.util.stream.Collectors;

/**
 * 编号720
 * 词典中最长的单词
 * <a href="https://leetcode-cn.com/problems/longest-word-in-dictionary/"></a>
 *
 * 给出一个字符串数组words组成的一本英语词典。
 * 从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1:
 * 输入: words = ["w","wo","wor","worl", "world"]
 * 输出: "world"
 * 解释:
 * 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
 *
 * 示例 2:
 * words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 * 输出: "apple"
 * 解释:
 * "apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
 *
 * 注意:
 * 所有输入的字符串都只包含小写字母。
 * words数组长度范围为[1,1000]。
 * words[i]的长度范围为[1,30]。
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/4
 */
public class LongestWordInDictionary {

    public static void main(String[] args) {

    }


    public class Trie{
        private Node root;
        private int dictSize=26;

        /**
         * 参数校验
         * @param str
         * @return
         */
        private boolean valid(String str){
            if(Objects.isNull(str)|| str.length()==0){
                return Boolean.FALSE;
            }
            return Boolean.TRUE;
        }

        /**
         * 参数校验
         * words数组长度范围为[1,1000]。
         * words[i]的长度范围为[1,30]。
         * @param strs
         * @return
         */
        private boolean valid(String[] strs){
            if(Objects.isNull(strs)|| strs.length<1||strs.length>1000){
                return Boolean.FALSE;
            }
            return Boolean.TRUE;
        }

        /**
         * 词典中最长的单词
         * 思路1->
         * 取出所有正常且是最终字符的节点 每个节点路径拼接为String
         * 放入list
         * 比较长度，留下最长（可能有多个）
         * 排序逐个字符比较顺序
         *
         * 思路2->
         * 取出所有正常且是最终字符的节点
         * 放入LinkedList或list 或者队列
         * 比较size
         * 如果有size 一样的情况出现
         * 比较队列头开始的节点谁更靠左
         *
         *
         * @return
         */
        public String longestWord() {
            // TODO: 2019/7/16 没有思路
            String result="";



            return result;
        }



        /**
         * 新增
         * @param srts
         */
        public void insert(String[] srts){
            if(!this.valid(srts)){
                return;
            }
            for (String str:srts){
                this.insert(str);
            }
        }

        /**
         * 新增
         * 已经出现的字符 如果重复出现则count++
         *
         * @param str
         */
        public void insert(String str){
            if(!this.valid(str)){
                return;
            }
            if(Objects.isNull(root)){
                root=new Node(Boolean.FALSE,new Node[dictSize],(char)0,0,0,null);
            }
            Node curNode=root;
            int diff;
            for(int i=0;i<str.length();i++){
                diff=str.charAt(i)-'a';
                if(Objects.isNull(curNode.nexts[diff])){
                    curNode.nexts[diff]=new Node(Boolean.FALSE,new Node[dictSize],str.charAt(i),i+1,0,curNode);
                }
                else{
                    curNode.nexts[diff].count++;
                }
                curNode=curNode.nexts[diff];
            }
            curNode.isLast=Boolean.TRUE;
        }


        /**
         * 完全匹配
         * @param str
         * @return
         */
        public boolean search(String str){
            if(!this.valid(str)){return Boolean.FALSE;}
            Node curNode=root;
            int diff;
            for (int i=0;i<str.length();i++){
                diff=str.charAt(i)-'a';
                if(Objects.isNull(curNode.nexts[diff])){
                    return Boolean.FALSE;
                }
                curNode=curNode.nexts[diff];
            }
            return curNode.isLast;
        }

        /**
         * 获取完整前缀
         *
         * @param node
         * @return
         */
        public String getPrefix(Node node){
            StringBuffer stringBuffer=new StringBuffer();
            if(Objects.isNull(node)){
                return stringBuffer.toString();
            }
            stringBuffer.append(node);
            while (node.loader==null){
                node=node.loader;
                stringBuffer.append(node.word);
            }

            return stringBuffer.reverse().toString();
        }

        private class Node{
            private boolean isLast;
            private Node[] nexts;
            private char word;
            private int depth;
            private int count;
            private Node loader;
            public Node(boolean isLast, Node[] nexts, char word,int depth,int count,Node loader) {
                this.isLast = isLast;
                this.nexts = nexts;
                this.word = word;
                this.depth=depth;
                this.count=count;
                this.loader=loader;
            }

            public Node() {
            }
        }


    }



}
